package  main.java.leetcode.editor.cn;
//2023-05-26 21:14:29
//给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。 
//
// 二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求
//： 
//
// 
// 路径途经的所有单元格的值都是 0 。 
// 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。 
// 
//
// 畅通路径的长度 是该路径途经的单元格总数。 
//
// 
//
// 示例 1： 
//
// 
//输入：grid = [[0,1],[1,0]]
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
//输出：4
// 
//
// 示例 3： 
//
// 
//输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
//输出：-1
// 
//
// 
//
// 提示： 
//
// 
// n == grid.length 
// n == grid[i].length 
// 1 <= n <= 100 
// grid[i][j] 为 0 或 1 
// 
// Related Topics 广度优先搜索 数组 矩阵 👍 311 👎 0

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class ShortestPathInBinaryMatrix {

    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new ShortestPathInBinaryMatrix().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    int[][] count;

    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid[0][0] == 1){
            return -1;
        }
        int m = grid.length;

        //记录
        count = new int[m][m];

        for(int[] arr : count){
            Arrays.fill(arr,Integer.MAX_VALUE);
        }

        Deque<int[]> deque = new ArrayDeque<>();
        deque.push(new int[]{0,0});

        int step = 1;
        count[0][0] = 1;
        while (!deque.isEmpty()){
            int size = deque.size();
            step++;
            while (size-->0){
                int[] cur = deque.pollFirst();
                for(int[] dir : dirs){

                    int nx = cur[0]+dir[0];
                    int ny = cur[1]+dir[1];

                    //越界判断，超过则退回
                    if(nx<0 || nx>=m || ny<0 || ny>=m){
                        continue;
                    }

                    if(grid[nx][ny] == 1 || count[nx][ny] != Integer.MAX_VALUE){
                        continue;
                    }

                    count[nx][ny] = Math.min(count[nx][ny],step);
                    deque.addLast(new int[]{nx,ny});

                }
            }
        }

        return count[m-1][m-1] == Integer.MAX_VALUE ? -1 :  count[m-1][m-1];
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
